﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Xml.Serialization;
using System.Drawing;

namespace GArphics
{
    /// <summary>
    /// Tree-class defines the structure of the binary tree and the related operations,
    /// such as creating a new random tree and mutating/crossing trees.
    /// </summary>
    public class Tree : IComparable
    {
        /// <summary>
        /// Root-node of the tree.
        /// </summary>
        public Node RootNode = null;

        /// <summary>
        /// A boolean determinig whether red channel should be disabled or not.
        /// </summary>
        public bool RedChannelModifier = false;
        /// <summary>
        /// Static value for the red color channel. Must be between 0 and 255.
        /// </summary>
        public int RedChannelValue = 0;
        /// <summary>
        /// A boolean determinig whether green channel should be disabled or not.
        /// </summary>
        public bool GreenChannelModifier = false;
        /// <summary>
        /// Static value for the green color channel. Must be between 0 and 255.
        /// </summary>
        public int GreenChannelValue = 0;
        /// <summary>
        /// A boolean determinig whether blue channel should be disabled or not.
        /// </summary>
        public bool BlueChannelModifier = false;
        /// <summary>
        /// Static value for the blue color channel. Must be between 0 and 255.
        /// </summary>
        public int BlueChannelValue = 0;

        /// <summary>
        /// Picture is drawn on X-axis from Xmin to Xmax
        /// </summary>
        public double Xmin = -1d;
        /// <summary>
        /// Picture is drawn on X-axis from Xmin to Xmax
        /// </summary>
        public double Xmax = 1d;
        /// <summary>
        /// Picture is drawn on Y-axis from Ymin to Ymax
        /// </summary>
        public double Ymin = -1d;
        /// <summary>
        /// Picture is drawn on Y-axis from Ymin to Ymax
        /// </summary>
        public double Ymax = 1d;
        /// <summary>
        /// Fitness of the tree, similarity when compared to the target-image. Zero means completely similar.
        /// </summary>
        public float Fitness = 0;

        /// <summary>
        /// Class.Random-object used to generate the randomized data.
        /// </summary>
        private static Random _oRandomizer = new Random();

        /// <summary>
        /// Empty constructor. No rootnode is set and tree can't be used. Rootnode must be set later.
        /// </summary>
        public Tree()
        {
        }

        /// <summary>
        /// Creates a new tree based on the provided root-node.
        /// </summary>
        /// <param name="RootNode">Rootnode for the tree.</param>
        public Tree(Node RootNode)
        {
            this.RootNode = RootNode;
        }

        /// <summary>
        /// Goes through the tree and calculates the value on the provided coordinates, according to thefunction described by the tree. 
        /// </summary>
        /// <param name="X">X-coordinate</param>
        /// <param name="Y">Y-coordinate</param>
        /// <returns>Value of the function on the corresponding coordinates.</returns>
        public double GetValue(double X, double Y)
        {
            if (RootNode != null)
                return RootNode.GetValue(X, Y);

            return Operator.FailValue;
        }

        /// <summary>
        /// Creating a new randomized tree. Nodes and the color channel modifiers are both completely randomized according to the static parameters.
        /// </summary>
        /// <returns>New randomized tree.</returns>
        public static Tree CreateRandomTree()
        {
            Tree oNewTree = new Tree(); //Creating a new tree without rootnode

            while (oNewTree.RootNode == null)   //while no rootnode has been set...
            {
                try
                {
                    oNewTree.RootNode = CreateRandomRootNode(); //creating a new random rootnode
                }
                catch (Exception)   //Just to be sure...
                {
                    oNewTree.RootNode = null;
                }
            }

            if (Properties.Settings.Default.RandomizeColors)
            {
                oNewTree.RedChannelModifier = _oRandomizer.NextDouble() > Properties.Settings.Default.ColorChannelModifierProbability; //Randomizing the color-channels.
                oNewTree.GreenChannelModifier = _oRandomizer.NextDouble() > Properties.Settings.Default.ColorChannelModifierProbability;
                oNewTree.BlueChannelModifier = _oRandomizer.NextDouble() > Properties.Settings.Default.ColorChannelModifierProbability;

                oNewTree.RedChannelValue = _oRandomizer.Next(0, 256);
                oNewTree.GreenChannelValue = _oRandomizer.Next(0, 256);
                oNewTree.BlueChannelValue = _oRandomizer.Next(0, 256);
            }
            if (Properties.Settings.Default.RandomizeCoordinates)   //randomizing the coordinates
            {
                double dX1 = _oRandomizer.NextDouble() * Properties.Settings.Default.RandomizeXMultiplier - Properties.Settings.Default.RandomizeXSubstraction;
                double dX2 = _oRandomizer.NextDouble() * Properties.Settings.Default.RandomizeXMultiplier - Properties.Settings.Default.RandomizeXSubstraction;
                double dY1 = _oRandomizer.NextDouble() * Properties.Settings.Default.RandomizeYMultiplier - Properties.Settings.Default.RandomizeYSubstraction;
                double dY2 = _oRandomizer.NextDouble() * Properties.Settings.Default.RandomizeYMultiplier - Properties.Settings.Default.RandomizeYSubstraction;

                oNewTree.Xmin = Math.Min(dX1, dX2);
                oNewTree.Xmax = Math.Max(dX1, dX2);
                oNewTree.Ymin = Math.Min(dY1, dY2);
                oNewTree.Ymax = Math.Max(dY1, dY2);
            }

            return oNewTree;
        }

        /// <summary>
        /// Counts the depth of the deepest path of the provided node.
        /// </summary>
        /// <param name="Node">Node which depth is to be counted.</param>
        /// <returns>Depth of the node.</returns>
        public static int CountDepth(Node Node)
        {
            return CountDepth(Node, 0);
        }

        /// <summary>
        /// Counts the depth of the deepest path of the provided node.
        /// </summary>
        /// <param name="Node">Node which depth is to be counted.</param>
        /// <param name="CurrentNodeLevel">Depth of the current node, relative to the parent nodes.</param>
        /// <returns>Depth of the node.</returns>
        private static int CountDepth(Node Node, int CurrentNodeDepth)
        {
            int iChildLeftDepth = CurrentNodeDepth;
            int iChildRightDepth = CurrentNodeDepth;

            if (Node != null)
            {
                if (Node.LeftChild != null)
                {   //depth of the left child node
                    iChildLeftDepth = CountDepth(Node.LeftChild, CurrentNodeDepth + 1);
                }
                if (Node.RightChild != null)
                {   //depth of the right child node
                    iChildRightDepth = CountDepth(Node.RightChild, CurrentNodeDepth + 1);
                }
            }
            //returning the one which was greater
            if (iChildLeftDepth > iChildRightDepth)
                return iChildLeftDepth;

            return iChildRightDepth;
        }

        /// <summary>
        /// Creates a new random root-node with the appropriate randomized subnodes.
        /// </summary>
        /// <returns>New random root-node</returns>
        private static Node CreateRandomRootNode()
        {
            return CreateRandomNode(0);
        }

        /// <summary>
        /// Creates a new random node with the appropriate randomized subnodes.
        /// </summary>
        /// <param name="CurrentNodeDepth">Depth of the new node in the tree.</param>
        /// <returns>New random node</returns>
        private static Node CreateRandomNode(int CurrentNodeDepth)
        {
            CurrentNodeDepth++;

            Node oNewNode = new Node();

            //Creating a new operator-node, if minimum depth has not yet been reached or the randomizer says that operator-node shall be created
            if (!(CurrentNodeDepth >= Properties.Settings.Default.MaxTreeDepth) && (CurrentNodeDepth < Properties.Settings.Default.MinTreeDepth || _oRandomizer.NextDouble() <= Properties.Settings.Default.OperatorProbability))
            {
                oNewNode.Operator = GetRandomOperator();

                oNewNode.LeftChild = CreateRandomNode(CurrentNodeDepth);    //creating child-nodes
                oNewNode.RightChild = CreateRandomNode(CurrentNodeDepth);
            }
            else    //if maximum depth has been reached, operand-node is forced: !(CurrentNodeDepth >= MaxTreeDepth)
            {
                SetRandomOperand(ref oNewNode);
            }

            return oNewNode;
        }

        /// <summary>
        /// Randomizes the operator of the provided node, according to the set randomized probabilities
        /// </summary>
        /// <param name="oNewNode">Node which parameter is to be set.</param>
        private static void SetRandomOperand(ref Node oNewNode)
        {
            if (_oRandomizer.NextDouble() <= Properties.Settings.Default.ConstantValueProbability)  //determining if the new node shall be constant value, X or Y
            {
                oNewNode.Operand = Operands.VALUE;
                oNewNode.Value = _oRandomizer.NextDouble() * Properties.Settings.Default.ConstantValueMultiplier - Properties.Settings.Default.ConstantValueSubstraction;
            }
            else
            {
                if (_oRandomizer.NextDouble() <= Properties.Settings.Default.OperandXProbability)   //X or Y, determined by the parameter OperandXProbability
                {
                    oNewNode.Operand = Operands.X;
                }
                else
                {
                    oNewNode.Operand = Operands.Y;
                }
            }
        }

        /// <summary>
        /// Pics one operator at random.
        /// </summary>
        /// <returns>Randomized operator.</returns>
        private static Operators GetRandomOperator()
        {
            int iMaxValue = Enum.GetNames(typeof(Operators)).Length - 1;    //randomizing operator for the node
            int fOperator = _oRandomizer.Next(0, iMaxValue) + 1;

            return (Operators)fOperator;
        }

        /// <summary>
        /// Counts how many subnodes the provided node has in total.
        /// </summary>
        /// <param name="oParentTree">Node which subnodes are to be counted.</param>
        /// <returns>Count of the subnodes.</returns>
        public static int CountSubNodes(Node ParentTree)
        {
            return CountSubNodes(ParentTree, 0);
        }

        /// <summary>
        /// Counts how many subnodes the provided node has.
        /// </summary>
        /// <param name="oParentTree">Node which subnodes are to be counted.</param>
        /// <param name="SubNodeCount">How many nodes there were before this one.</param>
        /// <returns></returns>
        private static int CountSubNodes(Node oParentTree, int SubNodeCount)
        {
            if (oParentTree != null)
            {
                SubNodeCount++;

                if (oParentTree.LeftChild != null)
                    SubNodeCount = CountSubNodes(oParentTree.LeftChild, SubNodeCount);
                if (oParentTree.RightChild != null)
                    SubNodeCount = CountSubNodes(oParentTree.RightChild, SubNodeCount);
            }

            return SubNodeCount;
        }

        /// <summary>
        /// Finds the subnode which is located at the provided position and returns it.
        /// </summary>
        /// <param name="oNode">The parent node, which subnode is to be returned.</param>
        /// <param name="iTargetNode">Number of the node which is to be returned.</param>
        /// <returns>Subnode from the provided position or the last subnode if the provided position was higher than the amount of subnodes.</returns>
        private static Node GetSubnodeAt(Node ParentNode, int TargetNode)
        {
            int iCounter = 0;

            return GetSubnodeAt(ParentNode, ref iCounter, TargetNode);
        }

        /// <summary>
        /// Finds the subnode which is located at the provided position and returns it.
        /// </summary>
        /// <param name="oNode">The parent node, which subnode is to be returned.</param>
        /// <param name="iCount">Position of the parent node on the branch.</param>
        /// <param name="iTargetNode">Number of the node which is to be returned.</param>
        /// <returns>Subnode from the provided position or the last subnode if the provided position was higher than the amount of subnodes.</returns>
        private static Node GetSubnodeAt(Node ParentNode, ref int Counter, int TargetNodePosition)
        {
            Counter++;

            Node oReturnNode = ParentNode;

            if (Counter != TargetNodePosition)
            {
                if (ParentNode.LeftChild != null)
                {
                    Node oLeftChild = GetSubnodeAt(ParentNode.LeftChild, ref Counter, TargetNodePosition);

                    if (Counter == TargetNodePosition)
                    {
                        oReturnNode = oLeftChild;
                    }
                }
                if (ParentNode.RightChild != null && Counter != TargetNodePosition)
                {
                    Node oRightChild = GetSubnodeAt(ParentNode.RightChild, ref Counter, TargetNodePosition);

                    if (Counter == TargetNodePosition)
                    {
                        oReturnNode = oRightChild;
                    }
                }
            }

            return oReturnNode;
        }

        /// <summary>
        /// Performs the crossover-operation for the two provided parent-nodes and returns the two resulting childrens.
        /// Selects a node from both of the parents and switches them with each other, thus creating two offspings.
        /// Color-modulations and coordinates are crossed uniformly.
        /// </summary>
        /// <param name="Parent1">First parent</param>
        /// <param name="Parent2">Second parent</param>
        /// <param name="Child1">First child</param>
        /// <param name="Child2">Second child</param>
        public static void Cross(Tree Parent1, Tree Parent2, out Tree Child1, out Tree Child2)
        {
            Child1 = new Tree(Parent1.RootNode.Copy());
            Child2 = new Tree(Parent1.RootNode.Copy());

            {
                int iParent1SelectedNode = _oRandomizer.Next(0, CountSubNodes(Parent1.RootNode) + 1);
                int iParent2SelectedNode = _oRandomizer.Next(0, CountSubNodes(Parent2.RootNode) + 1);

                int iCounter = 0;
                Node oChild1TargetNode = GetSubnodeAt(Child1.RootNode, ref iCounter, iParent1SelectedNode);

                iCounter = 0;
                Node oChild2TargetNode = GetSubnodeAt(Child2.RootNode, ref iCounter, iParent2SelectedNode);

                SwapData(oChild1TargetNode, oChild2TargetNode);
            }

            {
                SelectRandomly(Parent1.RedChannelModifier, Parent2.RedChannelModifier, ref Child1.RedChannelModifier, ref Child2.RedChannelModifier);
                SelectRandomly(Parent1.GreenChannelModifier, Parent2.GreenChannelModifier, ref Child1.GreenChannelModifier, ref Child2.GreenChannelModifier);
                SelectRandomly(Parent1.BlueChannelModifier, Parent2.BlueChannelModifier, ref Child1.BlueChannelModifier, ref Child2.BlueChannelModifier);

                SelectRandomly(Parent1.RedChannelValue, Parent2.RedChannelValue, ref Child1.RedChannelValue, ref Child2.RedChannelValue);
                SelectRandomly(Parent1.GreenChannelValue, Parent2.GreenChannelValue, ref Child1.GreenChannelValue, ref Child2.GreenChannelValue);
                SelectRandomly(Parent1.BlueChannelValue, Parent2.BlueChannelValue, ref Child1.BlueChannelValue, ref Child2.BlueChannelValue);

                SelectRandomly(Parent1.Xmax, Parent2.Xmax, ref Child1.Xmax, ref Child2.Xmax);
                SelectRandomly(Parent1.Xmin, Parent2.Xmin, ref Child1.Xmin, ref Child2.Xmin);
                SelectRandomly(Parent1.Ymax, Parent2.Ymax, ref Child1.Ymax, ref Child2.Ymax);
                SelectRandomly(Parent1.Ymin, Parent2.Ymin, ref Child1.Ymin, ref Child2.Ymin);
            }
        }

        /// <summary>
        /// Selects the two targets randomy from the provided sources.
        /// </summary>
        /// <param name="Source1"></param>
        /// <param name="Source2"></param>
        /// <param name="Target1"></param>
        /// <param name="Target2"></param>
        private static void SelectRandomly(double Source1, double Source2, ref double Target1, ref double Target2)
        {
            if (_oRandomizer.Next() % 2 == 0)
            {
                Target1 = Source1;
                Target2 = Source2;
            }
            else
            {
                Target1 = Source2;
                Target2 = Source1;
            }
        }

        /// <summary>
        /// Selects the two targets randomy from the provided sources.
        /// </summary>
        /// <param name="Source1"></param>
        /// <param name="Source2"></param>
        /// <param name="Target1"></param>
        /// <param name="Target2"></param>
        private static void SelectRandomly(int Source1, int Source2, ref int Target1, ref int Target2)
        {
            if (_oRandomizer.Next() % 2 == 0)
            {
                Target1 = Source1;
                Target2 = Source2;
            }
            else
            {
                Target1 = Source2;
                Target2 = Source1;
            }
        }

        /// <summary>
        /// Selects the two targets randomy from the provided sources.
        /// </summary>
        /// <param name="Source1"></param>
        /// <param name="Source2"></param>
        /// <param name="Target1"></param>
        /// <param name="Target2"></param>
        private static void SelectRandomly(bool Source1, bool Source2, ref bool Target1, ref bool Target2)
        {
            if (_oRandomizer.Next() % 2 == 0)
            {
                Target1 = Source1;
                Target2 = Source2;
            }
            else
            {
                Target1 = Source2;
                Target2 = Source1;
            }
        }

        /// <summary>
        /// Swaps the data contained on the provided two nodes.
        /// </summary>
        /// <param name="Node1"></param>
        /// <param name="Node2"></param>
        private static void SwapData(Node Node1, Node Node2)
        {
            Node oTempNode = new Node();

            oTempNode.Operator = Node1.Operator;
            oTempNode.Value = Node1.Value;
            oTempNode.LeftChild = Node1.LeftChild;
            oTempNode.RightChild = Node1.RightChild;
            oTempNode.Operand = Node1.Operand;

            Node1.Operator = Node2.Operator;
            Node1.Value = Node2.Value;
            Node1.LeftChild = Node2.LeftChild;
            Node1.RightChild = Node2.RightChild;
            Node1.Operand = Node2.Operand;

            Node2.Operator = oTempNode.Operator;
            Node2.Value = oTempNode.Value;
            Node2.LeftChild = oTempNode.LeftChild;
            Node2.RightChild = oTempNode.RightChild;
            Node2.Operand = oTempNode.Operand;
        }

        /// <summary>
        /// Performs the mutate-operation on the tree, according to the set probabilities.
        /// </summary>
        /// <returns>Mutated tree. This a completely seperate object from the parent.</returns>
        public Tree Mutate()
        {
            int iTargetNode = _oRandomizer.Next(0, CountSubNodes(RootNode) + 1);

            int iCounter = 0;

            Node oNewNode = RootNode.Copy();

            Node oTargetNode = GetSubnodeAt(oNewNode, ref iCounter, iTargetNode);

            double dMultiplier = Properties.Settings.Default.MutateChangeColorProbability +
                                 Properties.Settings.Default.MutateChangeCoordinateProbability +
                                 Properties.Settings.Default.MutateChangeOperatorOperandProbability +
                                 Properties.Settings.Default.MutateNewBranchProbability;

            double dRandomizedValue = _oRandomizer.NextDouble() * dMultiplier;
            double dCounter = 0;

            Tree oNewTree = new Tree(oNewNode);

            oNewTree.RedChannelModifier = this.RedChannelModifier;
            oNewTree.GreenChannelModifier = this.GreenChannelModifier;
            oNewTree.BlueChannelModifier = this.BlueChannelModifier;

            oNewTree.RedChannelValue = this.RedChannelValue;
            oNewTree.GreenChannelValue = this.GreenChannelValue;
            oNewTree.BlueChannelValue = this.BlueChannelValue;


            oNewTree.Xmin = this.Xmin;
            oNewTree.Xmax = this.Xmax;
            oNewTree.Ymin = this.Ymin;
            oNewTree.Ymax = this.Ymax;


            if (dRandomizedValue <= (dCounter += Properties.Settings.Default.MutateNewBranchProbability))
            {
                Node oNewRoot = CreateRandomRootNode();

                oTargetNode.Operator = oNewRoot.Operator;
                oTargetNode.Value = oNewRoot.Value;
                oTargetNode.LeftChild = oNewRoot.LeftChild;
                oTargetNode.RightChild = oNewRoot.RightChild;
                oTargetNode.Operand = oNewRoot.Operand;
            }
            else if (dRandomizedValue <= (dCounter += Properties.Settings.Default.MutateChangeOperatorOperandProbability))
            {
                if (oTargetNode.Operand == Operands.VALUE || oTargetNode.Operand == Operands.X || oTargetNode.Operand == Operands.Y)
                {
                    SetRandomOperand(ref oTargetNode);
                }
                else
                {
                    oTargetNode.Operator = GetRandomOperator();
                }
            }
            else if (dRandomizedValue <= (dCounter += Properties.Settings.Default.MutateChangeColorProbability))
            {
                switch (_oRandomizer.Next(0, 6))
                {
                    case 0:
                        oNewTree.RedChannelModifier = _oRandomizer.Next() % 2 == 0;
                        break;
                    case 1:
                        oNewTree.GreenChannelModifier = _oRandomizer.Next() % 2 == 0;
                        break;
                    case 2:
                        oNewTree.BlueChannelModifier = _oRandomizer.Next() % 2 == 0;
                        break;
                    case 3:
                        oNewTree.RedChannelValue = _oRandomizer.Next(0, 256);
                        break;
                    case 4:
                        oNewTree.GreenChannelValue = _oRandomizer.Next(0, 256);
                        break;
                    case 5:
                        oNewTree.BlueChannelValue = _oRandomizer.Next(0, 256);
                        break;
                }
            }
            else
            {
                double dNewCoordinate = _oRandomizer.NextDouble() * Properties.Settings.Default.RandomizeXMultiplier - Properties.Settings.Default.RandomizeXSubstraction;

                switch (_oRandomizer.Next(0, 4))
                {
                    case 0:
                        oNewTree.Xmin = dNewCoordinate;
                        break;
                    case 1:
                        oNewTree.Xmax = dNewCoordinate;
                        break;
                    case 2:
                        oNewTree.Ymin = dNewCoordinate;
                        break;
                    case 3:
                        oNewTree.Ymax = dNewCoordinate;
                        break;
                }

                oNewTree.Xmin = Math.Min(oNewTree.Xmin, oNewTree.Xmax);
                oNewTree.Xmax = Math.Max(oNewTree.Xmin, oNewTree.Ymax);
                oNewTree.Ymin = Math.Min(oNewTree.Ymin, oNewTree.Ymax);
                oNewTree.Ymax = Math.Max(oNewTree.Ymin, oNewTree.Ymax);
            }

            return oNewTree;
        }

        public int CompareTo(object o)
        {
            if (o is Tree)
            {
                Tree oOtherTree = o as Tree;

                if (this.Fitness == oOtherTree.Fitness)
                    return 0;
                else if (oOtherTree.Fitness < this.Fitness)
                    return -1;
            }
            return 1;
        }
    }
}